n=1000;
m=5000;
X=[140,621,243,726,587,733,74,55,132,638,706,554,864,491,694,797,834,85,859,260,177,834,243,165,273,617,388,714,498,272,726,298,256,167,409,328,769,386,597,299,179,963,375,701,355,45,3,780,927,442,756,803,597,718,198,594,674,985,69,722,324,57,659,994,503,318,366,869,620,357,960,889,78,158,877,882,963,813,728,829,609,660,958,141,358,856,929,185,79,295,599,76,738,905,281,204,131,804,628,972,747,6,891,138,405,95,691,457,135,4,277,936,735,941,144,545,763,352,525,435,136,68,49,784,780,326,414,984,164,168,178,437,214,213,951,189,680,415,593,667,200,945,531,157,905,12,482,119,701,286,601,599,357,463,555,503,538,762,948,159,864,18,65,80,198,987,347,714,607,100,664,822,20,252,665,309,88,410,485,959,354,883,13,477,855,824,598,832,645,189,114,247,657,899,735,54,418,382,47,89,763,320,966,108,157,965,743,215,187,629,432,162,20,94,201,197,93,255,905,603,76,989,497,722,390,362,598,573,874,585,547,643,203,595,581,653,594,933,934,283,810,927,891,239,594,863,893,976,303,156,12,129,159,20,631,864,375,7,565,559,342,185,352,326,560,611,108,879,715,195,716,209,685,135,438,590,253,14,834,421,877,168,463,945,287,17,102,559,293,98,397,940,950,655,669,828,120,538,916,92,617,15,491,114,245,46,417,8,603,492,751,84,408,98,275,411,962,20,141,449,94,107,956,42,523,820,522,397,589,719,723,123,339,249,323,165,281,434,509,363,286,248,445,526,535,410,406,599,162,174,44,469,276,539,700,443,364,455,527,239,662,907,779,869,329,930,154,66,569,381,233,465,965,922,818,881,474,321,394,637,399,157,460,851,94,113,612,414,305,617,837,444,619,436,692,984,851,329,98,105,261,254,989,521,577,818,848,535,169,117,551,422,823,67,92,476,925,485,437,403,467,544,891,27,869,484,820,950,66,6,330,515,430,254,402,516,256,113,854,392,21,376,771,489,356,224,764,38,80,744,877,43,681,238,889,252,171,258,181,958,717,521,498,759,979,980,991,432,188,814,220,834,429,145,544,966,29,722,828,835,175,665,494,141,251,706,863,736,453,350,438,601,836,27,370,901,932,279,388,895,132,273,859,823,745,113,997,750,882,419,285,507,170,800,223,793,769,828,494,502,299,217,839,245,815,850,883,573,369,930,985,64,577,315,793,326,370,631,674,783,539,818,662,164,25,573,161,799,420,325,509,750,293,74,280,372,455,609,564,896,491,10,126,924,585,594,704,663,238,738,472,683,449,831,783,456,533,8,938,263,386,716,236,40,180,505,602,53,906,341,709,509,665,833,84,505,574,176,208,570,167,725,878,89,291,786,1000,670,885,2,836,522,149,185,115,685,319,846,460,1000,34,896,439,876,627,293,554,561,607,52,335,240,788,397,76,722,873,540,314,502,577,634,550,903,181,740,347,828,750,738,702,814,399,312,512,589,921,481,224,484,461,887,759,56,398,444,858,365,636,420,483,17,922,328,705,214,784,205,731,29,298,876,448,622,807,624,226,873,516,754,607,312,318,968,567,458,627,577,49,666,858,282,870,853,358,989,171,320,968,637,179,312,418,948,955,24,996,381,341,375,546,250,462,735,244,238,911,758,61,356,727,233,157,863,232,180,79,992,342,612,268,459,243,701,342,66,414,148,829,632,743,143,446,167,821,615,886,772,576,165,811,541,967,714,164,610,626,230,165,465,681,778,332,256,428,629,470,863,9,595,459,866,370,769,653,524,732,987,613,87,481,878,926,5,542,302,968,83,941,881,878,72,164,266,233,626,885,247,859,913,413,668,332,306,165,478,832,158,475,192,839,257,2,97,573,323,477,772,199,138,408,959,764,430,192,653,977,859,158,164,731,210,920,79,370,385,64,509,472,31,683,152,222,513,291,911,799,655,653,604,11,103,732,39,374,425,628,441,278,786,760,50,728,682,380,844,428,21,723,550,956,806,571,18,585,567,76,926,487,290,981,983,612,243,383,713,908,555,584,264,432,527,889,995,666,143,856,332,666,776,543,553,653,267,539,14,297,835,102,288,218,746,294,747,744,301,299,966,567,12,860,106,685,795,523,78,183,987,197,422,61,745,235,151,113,430,460,236,4,262,96,140,34,65,430,258,449,485,839,924,189,642,617,293,511,997,149,91,329,853,465,426,644,489,679,407,474,848,892,429,364,847,322,395,110,831,455,996,406,412,764,221,976,927,262,987,157,141,336,827,743,614,798,240,807,214,820,129,119,416,69,632,912,182,757,660,734,906,688,559,239,648,128,857,303,826,939,931,743,643,226,893,953,372,684,985,350,602,592,149,945,94,855,413,361,803,360,903,834,524,961,141,988,635,765,654,371,475,176,461,102,151,85,497,944,769,833,675,842,860,173,100,798,722,408,524,837,831,699,388,699,724,115,565,334,117,370,422,75,603,70,90,64,666,648,247,651,372,447,737,257,669,979,397,528,909,362,590,230,561,390,11,144,554,981,263,844,940,887,400,95,576,612,385,399,611,356,760,538,589,181,528,638,651,416,320,206,614,876,186,539,233,578,165,337,774,935,651,670,266,317,940,559,412,714,266,291,627,823,179,597,293,811,649,774,840,14,229,921,501,526,928,549,144,285,929,38,953,985,922,557,118,363,731,787,15,552,309,634,80,667,408,293,875,241,173,650,499,244,173,863,762,297,216,546,588,553,151,472,378,204,315,7,296,497,251,396,695,575,426,486,900,391,535,80,919,480,987,11,133,458,975,122,774,587,563,492,983,758,319,166,801,318,78,238,545,367,494,633,582,830,786,566,222,548,56,960,353,895,988,768,484,600,683,129,200,198,296,442,448,690,650,160,567,985,876,697,535,86,332,466,235,765,660,234,454,584,932,925,634,566,358,610,698,135,945,604,872,354,463,589,992,911,751,630,186,573,531,241,420,717,3,504,190,196,496,723,309,765,962,901,873,613,875,927,750,710,346,340,526,925,336,163,965,508,406,97,652,208,533,909,1000,316,437,1,240,932,159,343,82,522,931,650,934,5,82,985,88,917,117,648,355,65,892,6,785,865,944,256,12,972,770,324,481,411,697,511,688,892,400,864,717,600,101,867,161,685,340,943,209,341,306,320,486,589,530,61,339,359,499,339,667,168,728,761,73,235,543,114,614,652,139,294,390,22,666,256,547,677,247,777,792,100,385,260,183,9,226,41,452,492,689,99,544,396,769,73,927,674,256,480,802,724,1000,343,757,819,193,802,306,814,701,344,173,132,291,717,574,838,557,305,123,826,185,710,163,441,428,478,899,787,602,923,620,221,616,485,707,314,698,32,144,230,173,155,848,557,671,722,620,122,553,508,711,329,604,926,628,494,777,423,725,99,639,818,29,470,489,791,823,416,622,818,869,935,743,658,498,261,37,171,984,375,560,13,395,143,617,674,163,211,360,124,678,611,711,597,108,695,965,37,874,39,52,208,527,64,4,5,154,646,517,504,162,52,249,937,68,654,303,723,585,608,658,261,669,444,464,813,753,936,492,632,866,446,948,611,456,162,555,877,208,599,216,562,458,314,677,178,604,893,873,55,757,702,438,515,378,653,772,544,221,418,988,942,393,141,398,841,239,4,292,553,980,824,901,784,657,968,754,86,722,588,44,312,263,211,188,453,134,943,930,576,759,828,847,89,926,28,307,540,685,373,223,529,271,265,620,66,190,766,466,560,774,308,210,549,616,681,37,995,968,960,578,876,215,686,292,137,465,612,761,164,368,400,357,501,760,35,253,80,369,572,268,485,408,956,34,695,982,472,640,886,264,466,653,53,21,968,947,332,75,444,435,535,226,506,357,965,295,901,329,259,330,490,137,687,513,972,372,805,411,782,597,452,878,764,153,362,713,19,965,740,291,740,526,55,354,949,287,666,100,919,959,506,618,921,935,356,736,980,64,158,950,213,796,319,906,903,72,763,84,526,97,72,409,460,59,187,632,152,43,531,432,682,959,141,896,488,528,87,21,292,23,869,464,68,317,167,845,241,994,928,445,657,383,744,429,645,947,155,461,123,458,57,330,476,97,948,660,127,660,765,496,69,680,935,304,836,513,746,974,716,213,761,628,740,95,885,823,430,149,248,56,766,427,226,2,247,302,536,862,287,961,576,570,446,891,750,389,771,519,970,429,151,835,167,898,352,273,677,488,143,698,345,1,34,190,776,648,699,285,807,351,719,945,526,658,455,801,313,306,347,399,638,307,666,331,105,502,596,494,658,359,48,88,22,456,942,411,338,493,774,974,140,134,231,882,858,824,305,424,144,508,883,698,494,646,550,933,367,752,224,85,124,205,290,105,855,294,442,979,528,24,178,601,260,59,807,751,345,133,259,914,115,453,267,950,226,592,274,634,970,200,924,263,905,320,668,188,900,922,670,788,99,873,902,287,777,206,199,717,461,343,813,350,339,76,52,821,627,825,430,784,760,447,737,834,427,602,614,481,742,492,347,793,666,600,778,374,185,352,680,758,268,408,351,581,631,361,533,78,32,903,602,145,699,451,246,72,401,394,928,601,660,708,776,767,389,646,806,393,270,344,361,737,433,503,554,925,511,4,854,618,537,396,615,125,403,62,419,608,299,232,755,211,415,203,565,952,300,866,219,917,224,134,402,574,129,221,908,528,267,758,615,336,998,975,116,482,118,408,728,890,426,5,182,871,581,903,371,186,792,652,248,780,549,627,76,77,838,272,399,710,596,966,296,768,864,560,809,626,582,919,326,551,733,248,945,725,808,450,328,951,72,92,189,556,255,133,550,639,326,714,515,493,81,140,266,810,294,952,222,492,866,29,612,37,684,897,484,502,255,948,982,727,892,219,107,832,669,910,568,299,900,851,294,375,946,809,132,54,24,413,356,720,530,457,626,983,895,488,536,288,330,499,108,936,44,480,400,661,280,789,178,977,445,913,994,323,951,539,727,109,271,681,737,663,590,811,592,10,294,86,596,989,82,569,899,116,337,547,550,165,398,563,484,481,91,206,702,945,673,852,889,334,889,204,784,439,71,580,967,399,138,457,168,693,38,613,306,458,617,868,725,326,49,774,351,28,13,321,570,921,519,268,932,33,864,484,198,682,988,194,789,7,250,307,748,534,126,208,288,499,230,244,579,859,432,560,938,185,51,74,151,804,833,537,983,623,932,259,268,391,901,143,517,1,990,820,17,194,162,984,336,429,736,121,106,633,100,176,53,168,325,9,420,25,664,357,994,478,251,208,59,863,651,443,724,293,487,410,526,808,610,767,567,962,813,638,601,706,243,399,41,137,252,711,697,440,122,535,630,368,735,779,450,377,845,228,868,52,212,847,723,1,815,532,599,577,975,368,648,892,951,307,580,485,895,539,774,482,385,767,26,189,775,940,146,53,507,692,867,189,413,658,337,315,888,567,671,347,845,697,255,730,471,982,960,659,918,437,507,237,900,165,430,355,699,964,737,883,189,738,68,928,98,203,638,544,998,41,687,46,224,823,7,793,836,967,757,355,729,53,161,963,612,474,498,60,787,530,217,275,91,974,332,893,675,187,356,247,607,761,479,220,142,260,487,195,116,575,649,661,169,868,231,867,863,453,191,903,656,726,769,526,166,297,117,717,105,857,226,32,173,127,768,516,705,976,343,462,809,116,982,274,589,113,101,438,703,438,699,484,873,529,98,683,805,961,285,614,915,621,457,340,519,539,569,598,232,889,112,301,522,80,915,697,941,324,628,530,67,542,328,99,886,914,666,330,600,864,950,970,529,367,607,546,221,342,778,123,771,969,312,645,751,426,904,618,521,149,891,401,412,99,390,709,736,497,955,588,232,790,320,425,660,624,582,266,336,111,355,450,411,959,537,488,689,531,54,494,50,653,338,435,977,279,187,553,509,78,252,448,955,465,681,777,955,518,653,876,550,894,309,891,303,596,75,652,479,105,227,67,591,307,993,766,273,954,625,823,367,809,669,550,787,83,603,772,254,523,317,993,866,795,831,806,311,30,404,956,905,62,761,555,968,175,537,836,239,698,7,296,405,779,391,246,344,955,781,513,85,639,540,815,449,95,353,28,531,823,286,45,463,649,472,349,197,786,760,492,864,849,933,450,64,315,177,472,992,921,608,976,696,984,356,784,412,904,996,452,876,302,480,145,402,939,158,434,871,970,864,406,262,934,420,527,623,449,443,637,941,62,418,730,504,216,500,860,740,624,198,910,568,796,226,902,345,250,165,608,229,913,889,546,360,465,11,663,465,158,69,324,846,625,85,822,868,686,877,481,136,239,201,530,754,919,524,903,4,192,476,857,335,486,265,57,158,482,426,920,225,824,168,709,267,690,416,460,972,106,525,209,944,563,548,681,175,537,487,609,411,652,131,340,965,586,498,370,584,754,745,316,452,249,627,369,812,809,100,396,761,61,174,707,221,526,144,130,48,905,234,662,175,367,883,330,712,332,555,341,159,144,145,266,668,873,622,303,914,814,711,726,426,798,791,655,830,119,52,69,294,656,293,476,487,759,362,745,823,251,820,578,522,108,297,962,552,846,561,39,948,202,171,19,319,437,1,70,595,383,584,802,232,404,553,222,27,30,850,219,354,354,22,402,729,463,97,412,608,970,853,393,170,572,415,378,448,386,123,927,916,308,108,754,735,247,180,833,571,67,91,320,673,342,847,604,708,431,497,689,404,684,384,717,309,300,772,659,709,886,420,10,26,360,168,635,657,976,296,15,968,607,723,854,197,873,905,504,516,470,161,152,269,372,749,828,444,51,408,207,927,887,919,583,203,282,541,695,384,152,429,934,473,249,668,743,757,418,812,711,432,219,690,105,946,371,169,485,183,488,837,989,637,503,361,319,625,130,10,238,491,229,697,713,54,72,973,82,1,505,958,79,928,719,99,213,763,119,237,632,902,923,450,117,671,862,772,825,748,361,647,454,770,697,982,813,671,391,558,975,297,86,889,810,516,553,757,835,705,234,18,902,977,372,888,151,742,898,766,133,626,134,756,465,318,187,107,876,109,99,119,694,294,570,764,512,77,769,734,507,858,339,975,654,489,859,365,844,857,509,498,915,69,857,234,878,942,491,304,132,686,982,521,984,415,140,663,863,890,879,808,301,440,939,285,640,341,281,163,698,320,630,813,724,900,866,632,638,610,762,109,760,653,470,635,652,716,92,443,473,195,403,410,761,722,713,122,508,669,357,497,939,187,797,681,110,935,802,718,167,602,503,691,277,39,470,381,34,333,490,311,485,145,686,140,776,681,221,608,546,970,408,240,543,714,539,957,459,455,592,869,595,7,746,993,805,453,339,456,810,915,39,283,395,802,655,655,889,60,31,974,451,554,856,374,668,14,927,377,971,43,692,211,465,280,347,895,918,264,167,899,677,293,570,759,819,336,238,682,812,11,223,165,54,511,607,357,4,158,897,789,724,395,622,762,138,389,515,518,858,263,489,638,370,883,379,811,254,378,603,525,442,454,726,587,227,737,852,820,406,98,809,114,576,39,431,185,444,790,753,212,201,707,337,361,113,341,939,128,131,337,87,496,137,421,739,362,315,782,727,684,866,299,960,487,78,136,989,425,817,163,269,683,889,850,71,940,178,28,312,493,538,555,569,956,563,721,478,489,733,88,425,235,241,840,292,588,366,388,226,448,608,661,335,283,676,6,652,704,550,367,972,58,499,850,617,927,431,153,968,376,57,254,496,219,810,897,103,273,241,549,246,968,833,267,568,898,393,734,511,884,852,822,38,912,687,277,168,595,750,277,776,608,407,664,254,267,493,126,929,919,310,147,863,9,149,598,239,874,25,579,608,344,364,177,639,494,893,997,324,680,711,485,286,488,423,566,947,780,562,359,64,325,189,284,775,865,683,228,788,978,746,915,607,477,6,257,237,68,437,65,895,20,914,818,530,656,866,345,653,796,825,125,278,515,78,546,493,386,803,183,487,34,614,64,645,682,699,949,962,250,752,120,345,809,191,251,252,232,319,600,926,829,443,263,866,697,2,804,482,459,45,38,489,98,980,273,209,63,74,93,165,777,692,741,248,702,606,168,125,449,902,771,597,990,983,781,540,16,696,874,76,516,242,1,993,763,365,575,491,540,875,865,855,791,923,277,710,483,528,674,244,426,72,763,218,432,422,88,653,383,472,165,917,629,881,873,511,668,351,40,691,809,375,682,791,622,708,538,898,577,380,735,753,395,596,535,102,729,806,727,916,422,186,900,284,871,202,165,955,53,820,342,410,679,388,319,748,62,608,931,916,119,762,745,285,300,586,167,31,163,761,234,625,93,158,775,521,313,333,557,358,95,475,856,615,133,532,728,313,197,406,512,340,237,915,744,390,726,506,155,551,485,206,25,316,725,581,374,973,563,235,25,631,672,485,366,18,211,670,261,435,53,70,441,635,883,29,530,342,615,884,635,270,439,69,229,518,757,430,569,679,389,315,18,286,786,376,425,763,610,795,455,468,725,272,183,16,546,938,257,589,201,305,864,442,602,679,492,765,925,82,889,223,760,301,631,467,493,494,992,43,960,521,381,827,821,916,969,947,888,66,844,329,604,760,217,965,429,610,656,819,901,383,493,997,507,553,904,383,327,726,211,521,479,74,575,632,614,803,551,597,688,651,443,780,878,249,542,270,960,368,601,464,838,535,142,762,230,848,813,361,458,769,218,213,687,317,333,123,951,772,337,300,607,655,390,269,265,117,976,21,11,761,453,746,583,153,298,93,658,368,159,553,181,261,214,439,86,403,432,597,688,911,848,402,598,493,478,292,52,955,829,707,263,595,166,147,696,789,955,390,557,484,148,639,792,28,278,504,734,610,343,525,849,244,779,239,382,829,986,538,592,107,191,703,299,376,739,426,330,940,576,637,305,905,590,828,291,653,898,15,78,620,610,795,114,268,954,513,566,487,242,325,651,213,318,17,623,735,124,423,619,637,385,651,261,472,637,622,911,657,514,876,750,720,705,767,868,774,709,562,39,196,335,927,223,161,224,969,227,64,914,131,429,664,23,950,978,74,911,288,651,158,143,807,623,407,869,906,662,722,333,961,943,75,839,255,27,232,759,279,920,52,59,621,247,749,897,168,582,958,390,391,215,502,872,769,615,200,469,107,704,441,465,174,928,668,788,582,695,953,418,204,389,322,921,117,818,925,287,881,555,605,289,77,316,984,717,601,600,258,505,954,795,889,217,473,425,576,277,51,588,732,513,583,266,922,268,403,988,918,721,79,97,669,761,680,472,357,462,855,498,496,281,456,478,36,462,35,978,509,107,526,57,506,236,904,7,652,874,296,551,283,183,692,686,104,308,699,45,563,604,427,947,783,334,139,737,201,718,491,252,189,604,503,278,42,916,424,189,433,565,450,658,993,970,591,44,397,740,275,147,892,926,454,45,569,551,13,420,177,107,889,430,152,50,134,483,796,624,566,499,191,588,275,982,65,953,881,770,373,848,281,896,103,804,423,487,69,292,605,615,691,780,918,768,236,293,988,25,888,208,826,977,904,831,19,81,820,589,432,408,990,88,326,766,309,910,6,369,387,213,980,115,710,570,928,218,35,203,680,847,254,517,684,671,140,415,208,573,641,932,118,862,786,909,921,396,860,141,563,212,971,907,376,63,325,515,785,676,212,926,66,125,183,742,932,334,353,882,76,785,137,744,274,197,416,926,211,202,814,703,591,998,446,29,91,436,429,201,360,687,303,677,707,35,786,378,643,301,529,826,166,622,570,304,132,492,720,67,170,184,274,847,809,945,739,531,957,904,648,564,54,914,260,728,346,810,63,916,360,140,819,839,534,642,670,20,149,347,531,364,360,223,953,714,297,453,66,117,316,501,181,938,682,310,332,647,247,569,775,617,635,603,735,47,189,55,700,533,132,538,264,266,876,494,313,266,831,624,51,332,418,546,348,93,108,537,470,939,618,488,913,675,837,331,670,692,418,884,388,66,249,610,407,811,279,645,588,997,84,380,623,703,854,599,405,667,564,141,386,819,379,975,421,937,925,587,903,429,997,50,55,907,20,114,912,386,183,677,825,341,663,360,997,718,856,749,793,759,498,249,625,199,563,975,115,307,803,19,586,322,102,400,964,400,726,818,844,28,398,468,441,666,48,484,205,849,728,258,535,254,911,349,666,240,17,894,163,746,543,187,703,676,446,317,843,601,886,99,42,242,827,372,482,650,439,856,591,337,879,336,127,730,434,162,637,212,901,502,390,276,578,260,174,961,379,236,12,199,132,315,626,949,743,685,542,895,797,933,956,13,260,887,186,410,579,407,666,149,184,327,83,99,978,981,104,427,792,602,552,17,808,428,204,652,296,757,76,136,961,994,515,237,47,301,382,822,106,156,825,914,720,367,122,55,241,638,468,490,450,449,965,575,315,389,665,160,936,294,501,742,179,783,372,489,296,716,797,246,472,601,243,364,255,32,740,694,503,151,426,332,362,383,334,810,51,215,80,799,446,471,455,911,420,941,31,306,200,107,870,739,668,223,511,770,173,857,104,458,770,153,667,547,225,799,800,353,362,568,49,955,755,936,348,725,282,507,5,807,462,562,570,996,206,868,469,644,968,835,38,714,12,99,222,438,174,70,444,612,56,106,988,787,69,689,643,207,967,289,157,120,666,466,39,713,847,954,246,370,154,788,774,310,948,741,907,781,673,518,3,403,355,909,618,95,414,787,341,670,130,503,591,957,532,546,943,122,925,913,144,748,114,422,712,86,186,471,578,809,555,766,556,135,605,39,889,912,421,229,24,80,564,437,396,623,413,658,906,976,194,927,941,587,344,512,621,955,447,162,460,240,51,782,192,318,149,578,404,573,346,663,806,575,867,596,266,293,956,186,766,682,118,846,468,974,477,866,844,812,105,613,639,668,993,182,405,954,852,717,288,110,54,90,678,994,705,267,243,39,49,450,613,760,863,437,94,717,711,493,205,393,706,880,341,45,325,583,805,443,288,816,550,915,928,332,289,601,397,82,534,749,341,835,6,674,175,316,938,80,264,40,641,947,858,939,902,545,112,192,719,15,987,427,911,197,120,31,453,597,192,842,308,608,542,660,193,945,989,308,312,984,687,619,23,856,815,367,352,130,640,977,811,952,164,143,842,883,542,251,764,701,104,714,947,679,70,77,390,444,465,492,696,884,437,526,591,546,291,443,741,559,456,146,466,661,219,339,368,469,227,110,501,705,567,90,853,322,452,639,846,283,659,172,274,628,601,818,985,865,493,383,100,488,965,492,291];